5.2 优先队列
优先队列 是一种特殊的队列，它与普通队列的区别在于：每个元素都有一个优先级，出队时，总是优先出队优先级最高的元素，而不是按照入队的顺序。
优先队列广泛应用于各种场景，如任务调度、路径规划等。它通常使用堆来实现，因为堆能保证高效的优先级出队和插入操作。
本节我们将介绍优先队列的基本概念、应用场景以及如何使用Go语言基于堆实现优先队列。
本节代码存放目录为 lesson11
概念及原理
优先队列 是一种抽象的数据结构，具有以下操作特性：
插入元素：将一个新元素插入到优先队列中。
删除优先级最高的元素：从优先队列中删除优先级最高的元素。
优先队列中的元素根据优先级进行排列，优先级可以是数值、字母、或任何可以比较的值。
优先队列通常使用堆来实现，堆的特性使得插入和删除操作都可以在 O(log n) 的时间复杂度内完成。
优先队列通常使用 堆 来实现，因为堆可以高效地维护一个动态集合，并快速地获取和移除优先级最高的元素。
最大堆 用于实现优先级递减的优先队列，即优先级最大的元素先出队。
最小堆 则用于实现优先级递增的优先队列，即优先级最小的元素先出队。
最大堆优先队列示意图
假设我们有一个优先队列，包含以下元素及其优先级：
(任务 A, 优先级 5)
(任务 B, 优先级 3)
(任务 C, 优先级 8)
(任务 D, 优先级 2)
(任务 E, 优先级 7)
使用最大堆维护这个优先队列的结构如下：
C(8)
/ \
E(7) A(5)
/ \
B(3) D(2)
在这个最大堆中，优先级最高的任务 C（8）位于堆顶，每次出队操作将移除堆顶元素，并调整堆的结构。
插入操作
插入新元素时，遵循堆的插入规则如下：
将新元素插入到堆的末尾。
通过 上滤 操作将新元素调整到正确的位置，以保持堆的性质。
操作示意如下所示：
初始堆状态：
C(8)
/ \
E(7) A(5)
/ \
B(3) D(2)
1. 插入任务 F（优先级 10）：
- 初始插入 F 到堆的末尾：
C(8)
/ \
E(7) A(5)
/ \ /
B(3) D(2) F(10)
- 上滤：F 的优先级高于 A，交换它们：
C(8)
/ \
E(7) F(10)
/ \ /
B(3) D(2) A(5)
- 上滤：F 的优先级高于 C，交换它们：
F(10)
/ \
E(7) C(8)
/ \ /
B(3) D(2) A(5)
这与上一节我们讲到的堆操作其实是差不多的，都是插入到末尾，之后根据大小/优先级进行上滤/下滤等操作，最终形成符合规则的堆结构。
删除操作
删除优先级最高的元素时，遵循堆的删除规则：
将堆的最后一个元素替换堆顶元素，并移除最后一个元素。
通过 下滤 操作将替换后的堆顶元素调整到正确的位置，以保持堆的性质。
操作示意如下所示：
初始堆状态：
F(10)
/ \
E(7) C(8)
/ \ /
B(3) D(2) A(5)
1. 删除任务 F（优先级 10）：
- 将堆的最后一个元素 A 替换到堆顶：
A(5)
/ \
E(7) C(8)
/ \
B(3) D(2)
- 下滤：C 的优先级高于 A，交换它们：
C(8)
/ \
E(7) A(5)
/ \
B(3) D(2)
删除的操作其实与上一节堆的删除也是一样的，只不过在上一节中，我们是通过节点进行比较，而在优先队列中则是使用优先级进行对比。
Go语言的实现
接下来我们使用Go语言基于最大堆实现优先队列的插入和删除操作，操作基本与上一节中的堆是一样的，只不过我们在元素上面加入了一个任务字段方便理解。
实现代码如下：
// item 定义节点结构
type item struct {
// 任务
task string
// 优先级
priority int
}
// PriorityQueue 定义优先队列结构
type PriorityQueue struct {
items []*item
}
// Insert 插入元素
func (pq *PriorityQueue) Insert(task string, priority int) {
pq.items = append(pq.items, &item{
task: task,
priority: priority,
})
pq.siftUp(len(pq.items) - 1)
}
// 上滤操作，维持最大堆性质
func (pq *PriorityQueue) siftUp(index int) {
parent := (index - 1) / 2
if parent >= 0 && pq.items[parent].priority < pq.items[index].priority {
pq.items[parent], pq.items[index] = pq.items[index], pq.items[parent]
pq.siftUp(parent)
}
}
// Remove 删除堆顶元素（优先级最高）
func (pq *PriorityQueue) Remove() *item {
if len(pq.items) == 0 {
return nil
}
// 将堆顶元素和最后一个元素交换，并删除堆顶元素
top := pq.items[0]
pq.items[0] = pq.items[len(pq.items)-1]
pq.items = pq.items[:len(pq.items)-1]
// 下滤操作，恢复堆序
pq.siftDown(0)
return top
}
// 下滤操作，维持最大堆性质
func (pq *PriorityQueue) siftDown(index int) {
left := 2*index + 1
right := 2*index + 2
largest := index
if left < len(pq.items) && pq.items[left].priority > pq.items[largest].priority {
largest = left
}
if right < len(pq.items) && pq.items[right].priority > pq.items[largest].priority {
largest = right
}
if largest != index {
pq.items[index], pq.items[largest] = pq.items[largest], pq.items[index]
pq.siftDown(largest)
}
}
func (pq *PriorityQueue) print() {
for _, v := range pq.items {
fmt.Printf("任务 %s, 优先级 %d\n", v.task, v.priority)
}
}
func main() {
pq := &PriorityQueue{}
pq.Insert("A", 5)
pq.Insert("B", 3)
pq.Insert("C", 8)
pq.Insert("D", 2)
pq.Insert("E", 7)
fmt.Println("优先队列: ")
pq.print()
fmt.Println("删除优先级最高的元素: ", pq.Remove())
fmt.Println("优先队列: ")
pq.print()
fmt.Println("删除优先级最高的元素: ", pq.Remove())
fmt.Println("优先队列: ")
pq.print()
}
执行结果如下所示：
优先队列:
任务 C, 优先级 8
任务 E, 优先级 7
任务 A, 优先级 5
任务 D, 优先级 2
任务 B, 优先级 3
删除优先级最高的元素: &{C 8}
优先队列:
任务 E, 优先级 7
任务 B, 优先级 3
任务 A, 优先级 5
任务 D, 优先级 2
删除优先级最高的元素: &{E 7}
优先队列:
任务 A, 优先级 5
任务 B, 优先级 3
任务 D, 优先级 2
在上面的实现中，我们通过 Insert 函数插入元素，并通过 Remove 函数删除优先级最高的元素。每次插入和删除都通过上滤和下滤操作来维持堆的性质。
小结
优先队列是一种常用的数据结构，它基于堆实现，使得插入和删除操作非常高效。优先队列广泛应用于任务调度、路径规划等场景。
通过本节课的学习，我们了解了优先队列的基本概念、操作原理以及在Go语言中的实现。
通过我们的例子也可以看出，假设我们有一批任务需要执行，而这些任务都有不同的权重，那么这时候我们使用优先队列来做就会显得特别简单。